package com.example.demo.leetcode;

/**
 * https://leetcode.cn/problems/intersection-of-two-linked-lists/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/03/06 11:22
 */
public class _160_相交链表 {

    public static void main(String[] args) {
        ListNode node = new ListNode(8, new ListNode(4, new ListNode(5)));
        ListNode headA = new ListNode(4, new ListNode(1, node));
        ListNode headB = new ListNode(5, new ListNode(6, new ListNode(1, node)));

        ListNode node1 = new ListNode(2, new ListNode(4));
        ListNode headA1 = new ListNode(1, new ListNode(9, new ListNode(1, node1)));
        ListNode headB1 = new ListNode(3, node1);


        ListNode headA2 = new ListNode(2, new ListNode(6, new ListNode(4)));
        ListNode headB2 = new ListNode(1, new ListNode(5));

        ListNode node3 = new ListNode(4, new ListNode(5, new ListNode(4, null)));
        ListNode headA3 = new ListNode(2, new ListNode(2, node3));
        ListNode headB4 = new ListNode(2, new ListNode(2, node3));

        ListNode intersectionNode = getIntersectionNode(headA3, headB4);
        System.out.println(intersectionNode.val);
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode headATemp = headA;
        ListNode headBTemp = headB;
        int AL = 0;
        while (headATemp != null) {
            AL++;
            headATemp = headATemp.next;
        }
        int BL = 0;
        while (headBTemp != null) {
            BL++;
            headBTemp = headBTemp.next;
        }

        if (AL >= BL) {
            headATemp = headA;
            headBTemp = headB;
        } else {
            headATemp = headB;
            headBTemp = headA;
        }

        int i = Math.abs(AL - BL);
        while (headATemp != null) {
            if (i != 0) {
                headATemp = headATemp.next;
                i--;
            } else {
                if (headATemp == headBTemp) {
                    return headATemp;
                }
                headATemp = headATemp.next;
                headBTemp = headBTemp.next;
            }
        }
        return null;
    }

}
